// 默认配置，指定节点 id、子节点属性名和父节点 id 属性名
const DEFAULT_CONFIG = {
    id: 'id',
    children: 'children',
    pid: 'pid'
  }
  
  // 合并用户配置和默认配置
  const getConfig = (config = {}) => Object.assign({}, DEFAULT_CONFIG, config)
  
  /**
   * 根据扁平列表生成树结构
   * @param {Array} list - 扁平节点列表
   * @param {Object} config - 配置项（可选）
   * @returns {Array} 树形结构数组
   */
  export const listToTree = (list, config = {}) => {
    const conf = getConfig(config)
    const nodeMap = new Map() // 用于存储节点映射，快速查找父节点
    const result = [] // 存放树结构的结果数组
    const { id, children, pid } = conf
  
    // 第一次遍历，初始化每个节点的 children 数组，并把节点存入 map
    for (const node of list) {
      node[children] = node[children] || []
      nodeMap.set(node[id], node)
    }
  
    // 第二次遍历，根据 pid 找到父节点，并把节点添加到父节点的 children 数组
    for (const node of list) {
      const parent = nodeMap.get(node[pid])
      if (parent) {
        parent[children].push(node)
      } else {
        // 没有父节点的直接放到结果数组中，作为根节点
        result.push(node)
      }
    }
  
    return result
  }
  
  /**
   * 将树结构转换成扁平列表
   * @param {Array} tree - 树结构数据
   * @param {Object} config - 配置项（可选）
   * @returns {Array} 扁平列表
   */
  export const treeToList = (tree, config = {}) => {
    const conf = getConfig(config)
    const { children } = conf
    const result = [...tree]
  
    for (let i = 0; i < result.length; i++) {
      if (!result[i][children]) continue
      // 把当前节点的子节点插入到当前节点后面
      result.splice(i + 1, 0, ...result[i][children])
    }
  
    return result
  }
  
  /**
   * 查找满足条件的第一个节点
   * @param {Array} tree - 树结构
   * @param {Function} func - 判断函数，接收节点，返回 boolean
   * @param {Object} config - 配置项（可选）
   * @returns {Object|null} 找到的节点或 null
   */
  export const findNode = (tree, func, config = {}) => {
    const conf = getConfig(config)
    const { children } = conf
    const list = [...tree]
  
    for (const node of list) {
      if (func(node)) return node
      node[children] && list.push(...node[children])
    }
  
    return null
  }
  
  /**
   * 查找满足条件的所有节点
   * @param {Array} tree - 树结构
   * @param {Function} func - 判断函数，接收节点，返回 boolean
   * @param {Object} config - 配置项（可选）
   * @returns {Array} 符合条件的节点数组
   */
  export const findNodeAll = (tree, func, config = {}) => {
    const conf = getConfig(config)
    const { children } = conf
    const list = [...tree]
    const result = []
  
    for (const node of list) {
      if (func(node)) result.push(node)
      node[children] && list.push(...node[children])
    }
  
    return result
  }
  
  /**
   * 查找满足条件的节点路径（返回第一条路径）
   * @param {Array} tree - 树结构
   * @param {Function} func - 判断函数，接收节点，返回 boolean
   * @param {Object} config - 配置项（可选）
   * @returns {Array|null} 节点路径数组或 null
   */
  export const findPath = (tree, func, config = {}) => {
    const conf = getConfig(config)
    const path = []
    const list = [...tree]
    const visitedSet = new Set()
    const { children } = conf
  
    while (list.length) {
      const node = list[0]
      if (visitedSet.has(node)) {
        // 已访问过该节点，说明此路径探索完毕，回溯
        path.pop()
        list.shift()
      } else {
        visitedSet.add(node)
        node[children] && list.unshift(...node[children]) // 将子节点加入队列前端，优先遍历
        path.push(node)
        if (func(node)) {
          // 找到目标节点，返回路径
          return path
        }
      }
    }
  
    return null
  }
  
  /**
   * 查找满足条件的所有节点路径（返回所有路径）
   * @param {Array} tree - 树结构
   * @param {Function} func - 判断函数，接收节点，返回 boolean
   * @param {Object} config - 配置项（可选）
   * @returns {Array} 符合条件节点的路径数组列表
   */
  export const findPathAll = (tree, func, config = {}) => {
    const conf = getConfig(config)
    const path = []
    const list = [...tree]
    const result = []
    const visitedSet = new Set()
    const { children } = conf
  
    while (list.length) {
      const node = list[0]
      if (visitedSet.has(node)) {
        // 回溯
        path.pop()
        list.shift()
      } else {
        visitedSet.add(node)
        node[children] && list.unshift(...node[children])
        path.push(node)
        if (func(node)) {
          result.push([...path]) // 记录当前路径的拷贝
        }
      }
    }
  
    return result
  }
  
  /**
   * 过滤树，返回满足条件的节点组成的树（不满足条件的节点及其子树被过滤掉）
   * @param {Array} tree - 树结构
   * @param {Function} func - 过滤函数，返回布尔值
   * @param {Object} config - 配置项（可选）
   * @returns {Array} 过滤后的树结构
   */
  export const filter = (tree, func, config = {}) => {
    const conf = getConfig(config)
    const children = conf.children
  
    function listFilter(list) {
      return list
        .map(node => ({ ...node })) // 浅拷贝，防止修改原数据
        .filter(node => {
          node[children] = node[children] && listFilter(node[children])
          // 当前节点满足条件 或 有子节点满足条件 保留
          return func(node) || (node[children] && node[children].length)
        })
    }
  
    return listFilter(tree)
  }
  
  /**
   * 遍历树，执行回调
   * @param {Array} tree - 树结构
   * @param {Function} func - 回调函数，接收节点，返回 true 可终止遍历
   * @param {Object} config - 配置项（可选）
   */
  export const forEach = (tree, func, config = {}) => {
    const conf = getConfig(config)
    const list = [...tree]
    const { children } = conf
  
    for (let i = 0; i < list.length; i++) {
      if (func(list[i])) {
        // 回调返回 true，终止遍历
        return
      }
      children && list[i][children] && list.splice(i + 1, 0, ...list[i][children])
    }
  }
  
  /**
   * 对树形数据执行映射转换
   * @param {Array} treeData - 树数据
   * @param {Object} opt - 配置，包含 children 属性名和 conversion 函数
   * @returns {Array} 转换后的树
   */
  export const treeMap = (treeData, opt) => {
    return treeData.map(item => treeMapEach(item, opt))
  }
  
  /**
   * 对单个节点执行映射转换
   * @param {Object} data - 单个节点
   * @param {Object} param1 - 包含 children 属性名和 conversion 函数
   * @returns {Object} 转换后的节点
   */
  export const treeMapEach = (data, { children = 'children', conversion }) => {
    const haveChildren = Array.isArray(data[children]) && data[children].length > 0
    const conversionData = conversion(data) || {}
  
    if (haveChildren) {
      return {
        ...conversionData,
        [children]: data[children].map(i =>
          treeMapEach(i, {
            children,
            conversion
          })
        )
      }
    } else {
      return {
        ...conversionData
      }
    }
  }
  
  /**
   * 递归遍历树结构，对每个节点执行回调
   * @param {Array} treeDatas - 树结构数组
   * @param {Function} callBack - 回调函数，接收当前节点和父节点
   * @param {Object} parentNode - 父节点，默认空对象
   */
  export const eachTree = (treeDatas, callBack, parentNode = {}) => {
    treeDatas.forEach(element => {
      const newNode = callBack(element, parentNode) || element
      if (element.children) {
        eachTree(element.children, callBack, newNode)
      }
    })
  }
  